package leetcode.code1438;

import java.util.Deque;
import java.util.LinkedList;

public class Solution {

	public int longestSubarray(int[] nums, int limit) {
		Deque<Integer> max = new LinkedList<>();
		Deque<Integer> min = new LinkedList<>();
		int ans = 0, l = -1, r = 0;
		while (r < nums.length) {
			int num = nums[r];
			while (!max.isEmpty() && nums[max.peekLast()] <= num) {// 维护最大值单调队列
				max.pollLast();
			}
			max.add(r);
			while (!min.isEmpty() && nums[min.peekLast()] >= num) {// 维护最小值单调队列
				min.pollLast();
			}
			min.add(r);
			while (l < r && Math.abs(nums[max.peekFirst()] - num) > limit) {// 通过limit调整左端l
				l = max.pollFirst();
			}
			while (l < r && min.peekFirst() < l) {// 因为大队调整造成小队左端失效
				min.pollFirst();
			}
			while (l < r && Math.abs(nums[min.peekFirst()] - num) > limit) {// 通过limit调整左端l
				l = min.pollFirst();
			}
			ans = Math.max(ans, r - l);// 有效窗口[l+1,r]
			r++;
		}
		return ans;
	}

}
